Hierarchical, unidirectional data structures are known and are commonly used to represent a variety of data. Such data structures can also be used to represent data elements with respect to a first axis, commonly a time axis, and wherein the data elements also have inter-relationships between themselves, such as child-parent hierarchies, etc.
One use for such data structures is to store time-based hierarchical data, such as the edits produced with a non-linear editor (NLE). In an NLE, data elements such as media sources, effects and filters are represented by objects which can be positioned and manipulated relative to a common time-based axis, or time line. Each data source can be represented by a clip object that has a duration which can be positioned relative to the time axis and is active (i.e.--generating an output) for all or a portion of that duration according to a time mask applied to the clip object by a user. The output of the source clip object can be a final output from the NLE or can be the input to another object in the NLE, such as a filter object or an effect object.
For example, a user may desire that a ten second portion of video information be output from a digital video stream with a total duration of forty seconds. The requested portion can be located from the tenth to the nineteenth second of the forty second video stream and it is desired to have that output at the thirty second point in the edit being produced, i.e. thirty seconds of some other output occurs and then ten seconds of this output. In such a case, the digital video stream can be represented within the NLE as a video source clip with a duration of forty seconds and is positioned by the user, with respect to a defined global time axis, such that the desired duration of the video source clip (ten to nineteen seconds) commences at the thirty second point on the global time line, i.e. the beginning of the clip is located at the twenty second point of the global timeline. The user then places a time mask along the appropriate portion of the clip (i.e. from thirty to thirty nine seconds relative to the global time line), activating the clip to output the requested duration of ten seconds, at the desired time. For the portions of the clip before and after the active duration, as indicated by the applied time mask, the clip is inactive and produces no output, although this can be subsequently changed by the user by adding additional time masks and/or changing the existing time mask.
In addition to being active or inactive, as mentioned above an object can be either the child or parent of another object. For example, the above mentioned video clip can be the child of a dissolve effect object and, in such a case, the output of the video clip is supplied to an input of the dissolve effect object for the specified duration and the dissolve effect processes the output from the video source clip and another video source clip to create an output comprising the desired dissolve effect between those clips. Also, an object can be the parent of another clip. For example, the dissolve effect object is the parent of the video clip described above.
In addition to the time-based change between active and inactive states, the hierarchical relationships between data elements can also change with time. For example, a thirty second video clip can be active and have no parent for a time t=0 to t=9 (i.e.--the output of the clip is output directly) and can be a child of a dissolve effect for a time t=10 to time t=19 (i.e.--the output of the clip is an input to a dissolve function) and can then be inactive for time t=20 onwards. In such a case, the parent-child relationships within the hierarchy of the NLE change with time.
It is believed that, in the past, hierarchical unidirectional data structures such as NLE edits have been represented as graph structures which represent the hierarchical relationships between data elements. When it was desired to produce a portion of an edit, the graph structure would be walked, visiting each data element in the graph. Each visited data element would then be required to specify whether it was active or inactive within the desired time portion of the edit, which (if any) of its one or more output connections is active and which other data elements are supplying it with input or inputs.
As an NLE edit can be very complex, consisting of many source data clips, effects objects and filter objects, such a graph can be very deep and performing a walk of such a graph can be computationally expensive to implement. Further, such a structure requires that each data element maintain its own list of when it is active and/or its hierarchical relationships with other data elements and this can make constructing and/or updating such a graph structure to reflect changes in the NLE a complex and computationally expensive operation to perform.
It is desired to have a novel method and system of representing and using hierarchical, unidirectional data structures such as NLE edits and the like which is relatively efficient to implement and which allows the data structures to be created and/or updated in a flexible manner.